/**
 * 升序数组
 * 2018年 03月 10日 星期六
 * @author fireway
 */
public class AscOrderArray {
    private long[] mLArray;

    private int mSize;

    public AscOrderArray(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    /**
     * 保持了insert()的线性查找，速度上有些缺陷不重要，这是由于
     * 在插入过程中平均一半的数据项都要移动，所以即使使用二分查找
     * 也不会明显提高insert()的速度，当然如果追求速度的话，可以
     * 将insert()的开始部分变为二分查找。
     * @param value
     */
    public void insert(long value) {
        if (mSize == mLArray.length) {
            System.out.println("Can not insert " + value);
            return;
        }

        int i = 0;
        for (i = 0; i < mSize; i++) {
            if (value < mLArray[i]) {
                break;
            }
        }
        for (int j = mSize; j > i; j--) {
            mLArray[j] = mLArray[j - 1];
        }
        mLArray[i] = value;
        mSize++;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize -1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    public int find(long searchValue) {
        int nL = 0;
        int nR = mSize - 1;

        while (nL <= nR)  {
            int nC = (nL + nR) / 2;
            if (searchValue == mLArray[nC]) {
                return nC;
            } else if (searchValue < mLArray[nC]) {
                nR = nC - 1;
            } else {
                nL = nC + 1;
            }
        }

        return -1;
    }

    public boolean delete(long value) {
        boolean ret = false;

        int i = find(value);
        if (-1 == i) {
            ret = false;
        } else {
            // 注意j这里应该是小于mSize - 1
            for (int j = i; j < mSize - 1; j++) {
                mLArray[j] = mLArray[j + 1];
            }
            mSize--;
            ret = true;
        }

        return ret;
    }
}

